package exec;

import java.util.Arrays;

/**
 * @Description 和大于等于 target 的最短子数组
 * @Date 2022/11/9 17:53
 * @Created by wangjun
 */
public class MinSubArrayLen {

    /**
     * 功能描述: 和大于等于 target 的最短子数组
     * <p>
     * 输入：target = 7, nums = [2,3,1,2,4,3]
     * 输出：2
     * 解释：子数组 [4,3] 是该条件下的长度最小的子数组。
     * <p>
     * 输入：target = 4, nums = [1,4,4]
     * 输出：1
     * <p>
     * 输入：target = 11, nums = [1,1,1,1,1,1,1,1]
     * 输出：0
     *
     * @Param: [target, nums]
     * <p>
     * 为了使用二分查找，需要额外创建一个数组 sums 用于存储数组 nums 的前缀和，其中 sums[i] 表示从 nums[0] 到 nums[i−1] 的元素和。
     * 得到前缀和之后，对于每个开始下标 i，可通过二分查找得到大于或等于 i 的最小下标 bound，使得 sums[bound]−sums[i−1]≥s，
     * 并更新子数组的最小长度（此时子数组的长度是 bound−(i−1)）。
     * @Return: int
     */
    public static int minSubArrayLen(int target, int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int[] sums = new int[nums.length + 1];
        sums[0] = 0;
        for (int i = 1; i < sums.length; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }
        int result = Integer.MAX_VALUE;
        boolean flag = false;
        for (int i = 0; i < sums.length - 1; i++) {
            int j = i + 1;
            while (j < sums.length) {
                if (sums[j] - sums[i] >= target) {
                    flag = true;
                    break;
                }
                flag = false;
                j++;
            }
            if (flag) {
                result = Math.min(j - i, result);
            }
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }


    public static void main(String[] args) {
        int len = minSubArrayLen3(15, new int[]{1, 2, 3, 4, 5});
        System.out.println(len);
    }

    /**
     * 功能描述: LeetCode官方解答
     *
     * @Param: [s, nums]
     * @Return: int
     */
    public static int minSubArrayLen1(int s, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int ans = Integer.MAX_VALUE;
        int[] sums = new int[n + 1];
        // 为了方便计算，令 size = n + 1
        // sums[0] = 0 意味着前 0 个元素的前缀和为 0
        // sums[1] = A[0] 前 1 个元素的前缀和为 A[0]
        // 以此类推
        for (int i = 1; i <= n; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }
        for (int i = 1; i <= n; i++) {
            int target = s + sums[i - 1];
            int bound = Arrays.binarySearch(sums, target);
            if (bound < 0) {
                bound = -bound - 1;
            }
            if (bound <= n) {
                ans = Math.min(ans, bound - (i - 1));
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }

    /**
     * 功能描述: 滑动窗口解决
     *
     * @Param: [target, nums]
     * @Return: int
     */
    public static int minSubArrayLen3(int target, int[] nums) {
        int start = 0, end = 0;
        int result = Integer.MAX_VALUE;
        int sum = 0;
        while (end < nums.length) {
            sum += nums[end];
            while (target <= sum) {
                result = Math.min(end - start + 1, result);
                sum -= nums[start];
                start++;
            }
            end++;
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}
